/*
 * @lc app=leetcode.cn id=322 lang=java
 *
 * [322] 零钱兑换
 */

// @lc code=start
class Solution {
    public int coinChange(int[] coins, int amount) {
        //物品可以无限取，完全背包，背包容量从左往右遍历，可以重复去
        //dp[j]代表重量为j的背包装满所需最少的物品数（硬币数）
        //最少的装满背包方案dp[j]=Math.min(d[j-coins[i]]+1,dp[j]);
        //dp[0]=0;其他赋值为最大值，但是+1后会变成最小值！！所以，d[j-coins[i]]还是最大值时，不要处理
        int[] dp=new int[amount+1];
        Arrays.fill(dp,Integer.MAX_VALUE);
        dp[0]=0;
        //遍历顺序因为组合数还是排列数都不影响求最小的dp[j],可以任意
        //这里外层遍历物品，内层遍历背包
        for(int i=0;i<coins.length;i++){
            for(int j=coins[i];j<=amount;j++){
                if(dp[j-coins[i]]!=Integer.MAX_VALUE){
                    dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
                }  
            }
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];


    }
}
// @lc code=end

